package com.sheepone.util.algorithm;

import com.sheepone.util.algorithm.analysis.IntegerAnalysisUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Miss.杨
 * @description 矩阵工具类
 * @since 2024/3/4 - 14:23
 */
public class MatrixUtil {

    public static boolean isSquareMatrix(int[][] matrix) {
        if (matrix == null) {
            return false;
        }
        return matrix.length == matrix[0].length;
    }

    private static void checkSquareMatrix(int[][] matrix) {
        if (!isSquareMatrix(matrix)) {
            throw new IllegalArgumentException("matrix must be a square matrix");
        }
    }

    /**
     * 将一个 n × n 的二维矩阵 matrix顺时针旋转 90 度
     *
     * @param matrix n × n 的二维矩阵 matrix
     * @time-complexity O(n ^ 2)
     * @space-complexity O(1)
     */
    public static void rotate(int[][] matrix) {
        checkSquareMatrix(matrix);
        int n = matrix.length, i = 0, j = 0;
        do {
            for (int k = j; k < n - j - 1; k++) {
                IntegerAnalysisUtil.swapInMatrix(matrix, i, k, k, n - j - 1);
                IntegerAnalysisUtil.swapInMatrix(matrix, i, k, n - i - 1, n - k - 1);
                IntegerAnalysisUtil.swapInMatrix(matrix, i, k, n - k - 1, i);
            }
            i++;
            j++;
        } while (i <= n / 2);
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        int u = 0, d = matrix.length - 1, l = 0, r = matrix[0].length - 1;
        List<Integer> list = new ArrayList<>();
        int i, j;
        while (true) {
            i = u;
            j = l - 1;
            while (++j <= r) {
                list.add(matrix[i][j]);
            }
            j--;
            u++;
            if (u > d) {
                break;
            }
            while (++i <= d) {
                list.add(matrix[i][j]);
            }
            i--;
            r--;
            if (l > r) {
                break;
            }
            while (--j >= l) {
                list.add(matrix[i][j]);
            }
            j++;
            d--;
            if (u > d) {
                break;
            }
            while (--i >= u) {
                list.add(matrix[i][j]);
            }
            l++;
            if (l > r) {
                break;
            }
        }
        return list;
    }

    public static void main(String[] args) {
        int[][] matrix = new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        rotate(matrix);
    }


}
